Quabl

DOI: 10.1126/science.298.5594.824

, 824 (2002);298 Science

et al.R. Milo

Network Motifs: Simple Building Blocks of Complex Networks

This copy is for your personal, non-commercial use only.

clicking here.colleagues, clients, or customers by

, you can order high-quality copies for yourIf you wish to distribute this article to others

here.following the guidelines

can be obtained byPermission to republish or repurpose articles or portions of articles

): February 4, 2013 www.sciencemag.org (this information is current as of

The following resources related to this article are available online at

http://www.sciencemag.org/content/298/5594/824.full.html

version of this article at:

including high-resolution figures, can be found in the onlineUpdated information and services,

http://www.sciencemag.org/content/suppl/2002/10/23/298.5594.824.DC1.html

can be found at: Supporting Online Material

http://www.sciencemag.org/content/298/5594/824.full.html#related

found at:

can berelated to this article A list of selected additional articles on the Science Web sites

http://www.sciencemag.org/content/298/5594/824.full.html#ref-list-1

, 7 of which can be accessed free:cites 19 articlesThis article

1038 article(s) on the ISI Web of Sciencecited by This article has been

http://www.sciencemag.org/content/298/5594/824.full.html#related-urls

100 articles hosted by HighWire Press; see:cited by This article has been

http://www.sciencemag.org/cgi/collection/cell_biol

Cell Biology

subject collections:This article appears in the following

registered trademark of AAAS.

CopyrightAmerican Association for the Advancement of Science, 1200 New York Avenue NW, Washington, DC 20005.

(print ISSN 0036-8075; online ISSN 1095-9203) is published weekly, except the last week in December, by theScience

on February 4, 2013www.sciencemag.orgDownloaded from

Cl concentrations in the Sajama ice core, and to

a number of other pedological and geomorpho-

logical features indicative of long-term dry cli-

mates (8, 11–14, 18). This decline in human

activity around the Altiplano paleolakes is seen

in most caves, with early and late occupations

separated by largely sterile mid-Holocene sed-

iments. However, a few sites, including the

caves of Tulan-67 and Tulan-68, show that

people did not completely disappear from the

area. All of the sites of sporadic occupation

are located near wetlands in valleys, near

large springs, or where lakes turned into wet-

lands and subsistence resources were locally

still available despite a generally arid climate

(7, 8, 19, 20).

Archaeological data from surrounding ar-

eas suggest that the Silencio Arqueolo´gico

applies best to the most arid areas of the

central Andes, where aridity thresholds for

early societies were critical. In contrast, a

weaker expression is to be expected in the

more humid highlands of northern Chile

(north of 20°S, such as Salar Huasco) and

Peru (21). In northwest Argentina, the Silen-

cio Arqueolo´gico is found in four of the six

known caves (22) [see review in (23)]. It is

also found on the coast of Peru in sites that

are associated with ephemeral streams (24).

The southern limit in Chile and northwest

Argentina has yet to be explored.

References and Notes

1. T. Dillehay, Science 245, 1436 (1989).

2. D. J. Meltzer et al., Am. Antiq. 62, 659 (1997).

3. T. F. Lynch, C. M. Stevenson, Quat. Res. 37, 117

(1992).

4. D. H. Sandweiss et al., Science 281, 1830 (1998).

5. L. Nu´n˜ez, M. Grosjean, I. Cartajena, in Interhemispher-

ic Climate Linkages, V. Markgraf, Ed. (Academic Press,

San Diego, CA 2001), pp. 105–117.

6. M. A. Geyh, M. Grosjean, L. Nu´n˜ez, U. Schotterer,

Quat. Res. 52, 143 (1999).

7. J. L. Betancourt, C. Latorre, J. A. Rech, J. Quade, K.

Rylander, Science 289, 1542 (2000).

8. M. Grosjean et al., Global Planet. Change 28,35

(2001).

9. C. Latorre, J. L. Betancourt, K. A. Rylander, J. Quade,

Geol. Soc. Am. Bull. 114, 349 (2002).

10. Charcoal in layers containing triangular points has

been

C dated at Tuina-1, Tuina-5, Tambillo-1, San

Lorenzo-1, and Tuyajto-1 between 13,000 and 9000

cal yr B.P. (table S1 and ﬁg. S1).

11. P. A. Baker et al., Science 291, 640 (2001).

12. G. O. Seltzer, S. Cross, P. Baker, R. Dunbar, S. Fritz,

Geology 26, 167 (1998).

13. L. G. Thompson et al., Science 282, 1858 (1998).

14. M. Grosjean, Science 292, 2391 (2001).

15. E. P. Tonni, written communication.

16. M. T. Alberdi, written communication.

17. J. Fernandez et al., Geoarchaeology 6, 251 (1991).

18. The histogram of middens is processed from (9).

19. M. Grosjean, L. Nu´n˜ez, I. Cartajena, B. Messerli, Quat.

Res. 48, 239 (1997).

20. The term Silencio Arqueolo´gico describes the mid-

Holocene collapse of human population at those

archaeological sites of the Atacama Desert that are

vulnerable to multicentennial or millennial-scale

drought. The term Silencio Archaeolo´gico does not

conﬂict with the presence of humans at sites that are

not susceptible to climate change, such as in spring

and river oases that drain large (Pleistocene) aquifers

or at sites where wetlands were created during the

arid middle Holocene, such as Tulan-67, Tulan-68,

and Laguna Miscanti.

21. M. Aldenderfer, Science 241, 1828 (1988).

22. A mid-Holocene hiatus is found at Inca Cueva 4,

Huachichocana 3, Pintocamayoc, and Yavi, whereas

occupation continued at the oases of Susques and

Quebrada Seca.

23. L. Nu´n˜ez et al., Estud. Atacamenos 17, 125 (1999).

24. D. H. Sandweiss, K. A. Maasch, D. G. Anderson, Sci-

ence 283, 499 (1999).

25. Grants from the National Geographic Society (5836-

96), the Swiss National Science Foundation

(21-57073), and Fondo Nacional de Desarrollo Cien-

tı´ﬁco y Tecnolo´gico (1930022) and comments by J. P.

Bradbury, B. Meggers, G. Seltzer, and D. Stanford are

acknowledged.

Supporting Online Material

www.sciencemag.org/cgi/content/full/298/5594/821/

DC1

Figs. S1 to S3

Tables S1 and S2

22 July 2002; accepted 9 September 2002

Network Motifs: Simple Building

Blocks of Complex Networks

R. Milo,

S. Shen-Orr,

S. Itzkovitz,

N. Kashtan,

D. Chklovskii,

U. Alon

Complex networks are studied across many ﬁelds of science. To uncover their

structural design principles, we deﬁned “network motifs,” patterns of inter-

connections occurring in complex networks at numbers that are signiﬁcantly

higher than those in randomized networks. We found such motifs in networks

from biochemistry, neurobiology, ecology, and engineering. The motifs shared

by ecological food webs were distinct from the motifs shared by the genetic

networks of Escherichia coli and Saccharomyces cerevisiae or from those found

in the World Wide Web. Similar motifs were found in networks that perform

information processing, even though they describe elements as different as

biomolecules within a cell and synaptic connections between neurons in Cae-

norhabditis elegans. Motifs may thus deﬁne universal classes of networks. This

approach may uncover the basic building blocks of most networks.

Many of the complex networks that occur in

nature have been shown to share global statis-

tical features (1–10). These include the “small

world” property (1–9) of short paths between

any two nodes and highly clustered connec-

tions. In addition, in many natural networks,

there are a few nodes with many more connec-

tions than the average node has. In these types

of networks, termed “scale-free networks” (4,

6), the fraction of nodes having k edges, p(k),

decays as a power law p(k) ⬃ k

–␥

(where ␥ is

often between 2 and 3). To go beyond these

global features would require an understanding

of the basic structural elements particular to

each class of networks (9). To do this, we

developed an algorithm for detecting network

motifs: recurring, significant patterns of inter-

connections. A detailed application to a gene

regulation network has been presented (11).

Related methods were used to test hypotheses

on social networks (12, 13). Here we generalize

this approach to virtually any type of connec-

tivity graph and find the striking appearance of

Departments of Physics of Complex Systems and

Molecular Cell Biology, Weizmann Institute of Sci-

ence, Rehovot, Israel 76100.

Cold Spring Harbor Lab-

oratory, Cold Spring Harbor, NY 11724, USA.

*To whom correspondence should be addressed. E-

mail: urialon@weizmann.ac.il

Fig. 1. (A) Examples

of interactions repre-

sented by directed

edges between nodes

in some of the net-

works used for the

present study. These

networks go from the

scale of biomolecules

(transcription factor

protein X binds regu-

latory DNA regions

of a gene to regulate

the production rate

of protein Y),

through cells (neuron

X is synaptically con-

nected to neuron Y),

to organisms (X

feeds on Y). (B) All 13 types of three-node connected subgraphs.

R EPORTS

25 OCTOBER 2002 VOL 298 SCIENCE www.sciencemag.org824

on February 4, 2013www.sciencemag.orgDownloaded from

motifs in networks representing a broad range

of natural phenomena.

We started with networks where the inter-

actions between nodes are represented by di-

rected edges (Fig. 1A). Each network was

scanned for all possible n-node subgraphs (in

the present study, n ⫽ 3 and 4), and the number

of occurrences of each subgraph was recorded.

Each network contains numerous types of n-

node subgraphs (Fig. 1B). To focus on those

that are likely to be important, we compared the

real network to suitably randomized networks

(12–16) and only selected patterns appearing in

the real network at numbers significantly higher

than those in the randomized networks (Fig. 2).

For a stringent comparison, we used random-

ized networks that have the same single-node

characteristics as does the real network: Each

node in the randomized networks has the same

number of incoming and outgoing edges as the

corresponding node has in the real network.

The comparison to this randomized ensemble

accounts for patterns that appear only because

of the single-node characteristics of the network

(e.g., the presence of nodes with a large number

of edges). Furthermore, the randomized net-

works used to calculate the significance of n-

node subgraphs were generated to preserve the

same number of appearances of all (n – 1)-node

subgraphs as in the real network (17, 18). This

ensures that a high significance was not as-

signed to a pattern only because it has a highly

significant subpattern. The “network motifs”

are those patterns for which the probability P of

appearing in a randomized network an equal or

greater number of times than in the real network

is lower than a cutoff value (here P ⫽ 0.01).

Patterns that are functionally important but not

statistically significant could exist, which

would be missed by our approach.

We applied the algorithm to several net-

works from biochemistry (transcriptional gene

regulation), ecology (food webs), neurobiology

(neuron connectivity), and engineering (elec-

tronic circuits, World Wide Web). The network

motifs found are shown in Table 1. Transcrip-

tion networks are biochemical networks re-

sponsible for regulating the expression of genes

in cells (11, 19). These are directed graphs, in

which the nodes represent genes (Fig. 1A).

Edges are directed from a gene that encodes for

a transcription factor protein to a gene transcrip-

tionally regulated by that transcription factor.

We analyzed the two best characterized tran-

scriptional regulation networks, corresponding

to organisms from different kingdoms: a eu-

karyote (the yeast Saccharomyces cerevisiae)

(20) and a bacterium (Escherichia coli)(11,

19). The two transcription networks show the

same motifs: a three-node motif termed “feed-

forward loop” (11) and a four-node motif

termed “bi-fan.” These motifs appear numerous

times in each network ( Table 1), in nonhomolo-

gous gene systems that perform diverse biolog-

ical functions. The number of times they appear

is more than 10 standard deviations greater than

their mean number of appearances in random-

ized networks. Only these subgraphs, of the 13

possible different three-node subgraphs (Fig.

1B) and 199 different four-node subgraphs, are

significant and are therefore considered net-

work motifs. Many other three- and four-node

subgraphs recur throughout the networks, but at

numbers that are less than the mean plus 2

standard deviations of their appearance in ran-

domized networks.

We next applied the algorithm to ecosystem

food webs (21, 22), in which nodes represent

groups of species. Edges are directed from a

node representing a predator to the node repre-

senting its prey. We analyzed data collected by

different groups at seven distinct ecosystems

(22), including both aquatic and terrestrial hab-

itats. Each of the food webs displayed one or

two three-node network motifs and one to five

four-node network motifs. One can define the

“consensus motifs” as the motifs shared by

networks of a given type. Five of the seven food

webs shared one three-node motif, and all seven

shared one four-node motif (Table 1). In con-

trast to the three-node motif (termed “three

chain”), the three-node feedforward loop was

underrepresented in the food webs. This sug-

gests that direct interactions between species at

a separation of two layers [as in the case of

omnivores (23 )] are selected against. The bi-

parallel motif indicates that two species that are

prey of the same predator both tend to share the

same prey. Both network motifs may thus rep-

resent general tendencies of food webs (21, 22).

We next studied the neuronal connectivity

network of the nematode Caenorhabditis ele-

gans (24). Nodes represent neurons (or neuron

Fig. 2. Schematic view of network motif detection. Network motifs are patterns that recur much

more frequently (A) in the real network than (B) in an ensemble of randomized networks. Each

node in the randomized networks has the same number of incoming and outgoing edges as does

the corresponding node in the real network. Red dashed lines indicate edges that participate in the

feedforward loop motif, which occurs ﬁve times in the real network.

150 200 250 300 350 400

0.005

0.01

0.015

Subnetwork size

Concentration of Feedforward loop

Real

Random

Fig. 3. Concentration C of

the feedforward loop motif

in real and randomized

subnetworks of the E. coli

transcription network (11).

C is the number of appear-

ances of the motif divided

by the total number of ap-

pearances of all connected

three-node subgraphs (Fig.

1B). Subnetworks of size S

were generated by choos-

ing a node at random and

adding to it nodes con-

nected by an incoming or

outgoing edge, until S

nodes were obtained, and

then including all of the

edges between these S

nodes present in the full

network. Each of the sub-

networks was randomized

(17, 18) (shown are mean and SD of 400 subnetworks of each size).

R EPORTS

www.sciencemag.org SCIENCE VOL 298 25 OCTOBER 2002 825

on February 4, 2013www.sciencemag.orgDownloaded from

classes), and edges represent synaptic connec-

tions between the neurons. We found the feed-

forward loop motif in agreement with anatomi-

cal observations of triangular connectivity struc-

tures (24). The four-node motifs include the

bi-fan and the bi-parallel (Table 1). Two of

these motifs (feedforward loop and bi-fan) were

also found in the transcriptional gene regulation

networks. This similarity in motifs may point to

a fundamental similarity in the design con-

straints of the two types of networks. Both net-

works function to carry information from sen-

sory components (sensory neurons/transcription

factors regulated by biochemical signals) to ef-

fectors (motor neurons/structural genes). The

feedforward loop motif common to both types

of networks may play a functional role in infor-

mation processing. One possible function of this

circuit is to activate output only if the input

signal is persistent and to allow a rapid deacti-

vation when the input goes off (11). Indeed,

many of the input nodes in the neural feedfor-

ward loops are sensory neurons, which may

require this type of information processing

to reject transient input fluctuations that are

inherent in a variable or noisy environment.

We also studied several technological net-

works. We analyzed the ISCAS89 benchmark

set of sequential logic electronic circuits (7, 25).

The nodes in these circuits represent logic gates

and flip-flops. These nodes are linked by direct-

ed edges. We found that the motifs separate the

circuits into classes that correspond to the cir-

cuit’s functional description. In Table 1, we

present two classes, consisting of five forward-

logic chips and three digital fractional multipli-

ers. The digital fractional multipliers share three

motifs, including three- and four-node feedback

loops. The forward logic chips share the feed-

forward loop, bi-fan, and bi-parallel motifs,

which are similar to the motifs found in the

genetic and neuronal information-processing

networks. We found a different set of motifs in

a network of directed hyperlinks between

World Wide Web pages within a single domain

(4). The World Wide Web motifs may reflect a

design aimed at short paths between related

pages. Application of our approach to nondi-

rected networks shows distinct sets of motifs in

networks of protein interactions and Internet

router connections (18).

None of the network motifs shared by the

food webs matched the motifs found in the gene

regulation networks or the World Wide Web.

Only one of the food web consensus motifs also

appeared in the neuronal network. Different

motif sets were found in electronic circuits with

different functions. This suggests that motifs

can define broad classes of networks, each with

specific types of elementary structures. The

motifs reflect the underlying processes that gen-

erated each type of network; for example, food

webs evolve to allow a flow of energy from the

bottom to the top of food chains, whereas gene

regulation and neuron networks evolve to pro-

cess information. Information processing seems

to give rise to significantly different structures

than does energy flow.

We further characterized the statistical sig-

nificance of the motifs as a function of network

size, by considering pieces of various sizes

(subnetworks) of the full network. The concen-

tration of motifs in the subnetworks is about the

same as that in the full network (Fig. 3). In

contrast, the concentration of the corresponding

subgraphs in the randomized versions of the

subnetworks decreases sharply with size. In

analogy with statistical physics, the number of

appearances of each motif in the real networks

Table 1. Network motifs found in biological and technological networks. The numbers of nodes and edges

for each network are shown. For each motif, the numbers of appearances in the real network (N

real

) and

in the randomized networks (N

rand

⫾ SD, all values rounded) (17, 18) are shown. The P value of all motifs

is P ⬍ 0.01, as determined by comparison to 1000 randomized networks (100 in the case of the World

Wide Web). As a qualitative measure of statistical signiﬁcance, the Z score ⫽ (N

real

– N

rand

)/SD is shown.

NS, not signiﬁcant. Shown are motifs that occur at least U ⫽ 4 times with completely different sets of

nodes. The networks are as follows (18): transcription interactions between regulatory proteins and genes

in the bacterium E. coli (11) and the yeast S. cerevisiae (20); synaptic connections between neurons in

C. elegans, including neurons connected by at least ﬁve synapses (24); trophic interactions in ecological

food webs (22), representing pelagic and benthic species (Little Rock Lake), birds, ﬁshes, invertebrates

(Ythan Estuary), primarily larger ﬁshes (Chesapeake Bay), lizards (St. Martin Island), primarily inverte-

brates (Skipwith Pond), pelagic lake species (Bridge Brook Lake), and diverse desert taxa (Coachella

Valley); electronic sequential logic circuits parsed from the ISCAS89 benchmark set (7, 25), where nodes

represent logic gates and ﬂip-ﬂops ( presented are all ﬁve partial scans of forward-logic chips and three

digital fractional multipliers in the benchmark set); and World Wide Web hyperlinks between Web pages

in a single domain (4) (only three-node motifs are shown). e, multiplied by the power of 10 (e.g., 1.46e6

⫽ 1.46 ⫻ 10

*Has additional four-node motif: (X3 Z, W; Y3 Z, W; Z3 W), N

real

⫽ 150, N

rand

⫽ 85 ⫾ 15, Z ⫽ 4. †Has additional

four-node motif: (X3 Y, Z; Y3 Z; Z3 W), N

real

⫽ 204, N

rand

⫽ 80 ⫾ 20, Z ⫽ 6. The three-node pattern (X3 Y, Z; Y3 Z;

Z3 Y) also occurs signiﬁcantly more than at random. It is not a motif by the present deﬁnition because it does not

appear with completely distinct sets of nodes more than U ⫽ 4 times. ‡Has additional four-node motif: (X3 Y;

Y3 Z, W; Z3 X; W3 X), N

real

⫽ 914, N

rand

⫽ 500 ⫾ 70, Z ⫽ 6. §Has two additional three-node motifs: (X3 Y, Z;

Y3 Z; Z3 Y), N

real

⫽ 3e5, N

rand

⫽ 1.4e3 ⫾ 6e1, Z ⫽ 6000, and (X3 Y, Z; Y3 Z), N

real

⫽ 5e5, N

rand

⫽ 9e4 ⫾ 1.5e3,

Z ⫽ 250.

Network Nodes Edges

real

rand

± SD

Z score

real

rand

± SD

Z score

real

rand

± SD

Z score

Gene regulation

(transcription)

Feed-

forward

loop

X Y

Z W

Bi-fan

E. coli 424 519 40 7 ± 3 10 203 47 ± 12

S. cerevisiae* 685 1,052 70 11 ± 4 14 1812 300 ± 40

Neurons X

Feed-

forward

loop

X Y

Z W

Bi-fan X

Y Z

Bi-

parallel

C. elegans† 252 509 125 90 ± 10 3.7 127 55 ± 13 5.3 227 35 ± 10

Food webs X

Three

chain

Y Z

Bi-

parallel

Little Rock 92 984 3219 3120 ± 50 2.1 7295 2220 ± 210

Ythan 83 391 1182 1020 ± 20 7.2 1357 230 ± 50

St. Martin 42 205 469 450 ± 10 NS 382 130 ± 20

Chesapeake 31 67 80 82 ± 4 NS 26 5 ± 2

Coachella 29 243 279 235 ± 12 3.6 181 80 ± 20

Skipwith 25 189 184 150 ± 7 5.5 397 80 ± 25

B. Brook 25 104 181 130 ± 7 7.4 267 30 ± 7

Electronic circuits

(forward logic chips)

Feed-

forward

loop

Bi-fan

Y Z

Bi-

parallel

s15850 10,383 14,240 424 2 ± 2 285 1040 1 ± 1 1200 480 2 ± 1

335

s38584 20,717 34,204 413 10 ± 3 120 1739 6 ± 2 800 711 9 ± 2

320

s38417 23,843 33,661 612 3 ± 2 400 2404 1 ± 1 2550 531 2 ± 2

340

s9234 5,844 8,197 211 2 ± 1 140 754 1 ± 1 1050 209 1 ± 1

200

s13207 8,651 11,831 403 2 ± 1 225 4445 1 ± 1 4950 264 2 ± 1

200

Electronic circuits

(digital fractional multipliers)

Y Z

Three-

node

feedback

loop

Bi-fan X Y

Z W

Four-

node

feedback

loop

s208 122 189 10 1 ± 1 9 4 1 ± 1 3.8 5 1 ± 1

s420 252 399 20 1 ± 1 18 10 1 ± 1 10 11 1 ± 1

s838‡

512 819 40 1 ± 1 38 22 1 ± 1 20 23 1 ± 1

World Wide Web

Feedback

with two

mutual

dyads

Y Z

Fully

connected

triad

Y Z

Uplinked

mutual

dyad

nd.edu§

325,729 1.46e6 1.1e5 2e3 ± 1e2 800 6.8e6 5e4±4e2 15,000 1.2e6 1e4 ± 2e2

5000

X Y

Z W

X Y

Z W

R EPORTS

25 OCTOBER 2002 VOL 298 SCIENCE www.sciencemag.org826

on February 4, 2013www.sciencemag.orgDownloaded from

appears to be an extensive variable (i.e., one

that grows linearly with the system size). These

variables are nonextensive in the randomized

networks. The existence of such variables may

be a unifying property of evolved or designed

systems. The decrease of the concentration C

with randomized network size S (Fig. 3) qual-

itatively agrees with exact results (2, 26)on

Erdos-Renyi random graphs (random graphs

that preserve only the number of nodes and

edges of the real network) in which C ⬃ 1/S.In

general, the larger the network is, the more

significant the motifs tend to become. This

trend can also be seen in Table 1 by comparing

networks of different sizes. The network motif

detection algorithm appears to be effective even

for rather small networks (on the order of 100

edges). This is because three- or four-node sub-

graphs occur in large numbers even in small

networks. Furthermore, our approach is not

sensitive to data errors; for example, the sets of

significant network motifs do not change in any

of the networks upon addition, removal, or

rearrangement of 20% of the edges at random.

In information-processing networks, the

motifs may have specific functions as elemen-

tary computational circuits (11). More general-

ly, they may be interpreted as structures that

arise because of the special constraints under

which the network has evolved (27). It is of

value to detect and understand network motifs

in order to gain insight into their dynamical

behavior and to define classes of networks and

network homologies. Our approach can be

readily generalized to any type of network,

including those with multiple “colors” of edges

or nodes. It would be fascinating to see what

types of motifs occur in other networks and to

understand the processes that yield given motifs

during network evolution.

References and Notes

1. S. H. Strogatz, Nature 410, 268 (2001).

2. B. Bollobas, Random Graphs (Academic, London, 1985).

3. D. Watts, S. Strogatz, Nature 393, 440 (1998).

4. A.-L. Baraba´si, R. Albert, Science 286, 509 (1999).

5. M. Newman, Proc. Natl. Acad. Sci. U.S.A. 98, 404

(2001).

6. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, A. L.

Barabasi, Nature 407, 651 (2000).

7. R. F. Cancho, C. Janssen, R. V. Sole, Phys. Rev. E 64,

046119 (2001).

8. R. F. Cancho, R. V. Sole, Proc. R. Soc. London Ser. B

268, 2261 (2001).

9. L. Amaral, A. Scala, M. Barthelemy, H. Stanley, Proc.

Natl. Acad. Sci. U.S.A. 97, 11149 (2000).

10. B. Huberman, L. Adamic, Nature 401, 131 (1999).

11. S. Shen-Orr, R. Milo, S. Mangan, U. Alon, Nature

Genet. 31, 64 (2002).

12. P. Holland, S. Leinhardt, in Sociological Methodol-

ogy, D. Heise, Ed. ( Jossey-Bass, San Francisco,

1975), pp. 1– 45.

13. S. Wasserman, K. Faust, Social Network Analysis

(Cambridge Univ. Press, New York, 1994).

14. N. Guelzim, S. Bottani, P. Bourgine, F. Kepes, Nature

Genet. 31, 60 (2002).

15. M. Newman, S. Strogatz, D. Watts, Phys. Rev. E 64,

6118 (2001).

16. S. Maslov, K. Sneppen, Science 296, 910 (2002).

17. The randomized networks used for detecting three-

node motifs preserve the numbers of incoming, outgo-

ing, and double edges with both incoming and outgoing

arrows for each node. The randomized networks used

for detecting four-node motifs preserve the above char-

acteristics as well as the numbers of all 13 three-node

subgraphs as in the real network. Algorithms for con-

structing these randomized network ensembles are de-

scribed (18). Additional information is available at

www.weizmann.ac.il/mcb/UriAlon.

18. Methods are available as supporting material on Sci-

ence Online.

19. D. Thieffry, A. M. Huerta, E. Perez-Rueda, J. Collado-

Vides, Bioessays 20, 433 (1998).

20. M. C. Costanzo et al., Nucleic Acids Res. 29,75

(2001).

21. J. Cohen, F. Briand, C. Newman, Community Food

Webs: Data and Theory (Springer, Berlin, 1990).

22. R. Williams, N. Martinez, Nature 404, 180 (2000).

23. S. Pimm, J. Lawton, J. Cohen, Nature 350, 669

(1991).

24. J. White, E. Southgate, J. Thomson, S. Brenner, Philos.

Trans. R. Soc. London Ser. B 314, 1 (1986).

25. F. Brglez, D. Bryan, K. Kozminski, Proc. IEEE Int. Symp.

Circuits Syst., 1929 (1989).

26. In Erdos-Renyi randomized networks with a ﬁxed

connectivity (2), the concentration of a subgraph

with n nodes and k edges scales with network size as

C ⬃ S

n–k–1

(thus, C ⬃ 1/S for the feedforward loop of

Fig. 3 where n ⫽ k ⫽ 3). The sole exception in Table

1 in which C should not vanish at large S is the

three-chain pattern in food webs where n ⫽ 3 and

k ⫽ 2.

27. D. Callaway, J. Hopcroft, J. Kleinberg, M. Newman, S.

Strogatz, Phys. Rev. E 64, 041902 (2001).

28. We thank S. Maslov and K. Sneppen for valuable

discussions. We thank J. Collado-Vides, N. Mar-

tinez, R. Govindan, R. Durbin, L. Amaral, R. Cancho,

S. Maslov, and K. Sneppen for kindly providing data,

as well as D. Alon, E. Domany, M. Elowitz, I. Kanter,

O. Hobart, M. Naor, D. Mukamel, A. Murray, S.

Quake, R. Raz, M. Reigl, M. Surette, K. Sneppen, P.

Sternberg, E. Winfree, and all members of our lab

for comments. We thank Caltech and the Aspen

Center for Physics for their hospitality during part

of this work. We acknowledge support from the

Israel Science Foundation, the Human Frontier Sci-

ence Program, and the Minerva Foundation.

Supporting Online Material

www.sciencemag.org/cgi/content/full/298/5594/824/DC1

Methods

Table S1

1 May 2002; accepted 10 September 2002

Progression of Vertebrate Limb

Development Through

SHH-Mediated Counteraction of

GLI3

Pascal te Welscher,

Aime´e Zuniga,

Sanne Kuijper,

Thijs Drenth,

Hans J. Goedemans,

Frits Meijlink,

Rolf Zeller

Distal limb development and speciﬁcation of digit identities in tetrapods are

under the control of a mesenchymal organizer called the polarizing region. Sonic

Hedgehog (SHH) is the morphogenetic signal produced by the polarizing region

in the posterior limb bud. Ectopic anterior SHH signaling induces digit dupli-

cations and has been suspected as a major cause underlying congenital mal-

formations that result in digit polydactyly. Here, we report that the polydactyly

of Gli3-deﬁcient mice arises independently of SHH signaling. Disruption of one

or both Gli3 alleles in mouse embryos lacking Shh progressively restores limb

distal development and digit formation. Our genetic analysis indicates that SHH

signaling counteracts GLI3-mediated repression of key regulator genes, cell

survival, and distal progression of limb bud development.

The Hedgehog (Hh) signaling pathway con-

trols many key developmental processes dur-

ing animal embryogenesis (1). In Drosophila

embryos, all known functions of Hh signaling

are mediated by the transcriptional effector

Cubitus interruptus (Ci) (2). Several ho-

mologs of Hh and Ci have been identified in

higher vertebrates. In particular, Sonic

Hedgehog (SHH) and the Ci homolog GLI3

are required for vertebrate limb development

(3– 6). GLI3 acts first during the initiation of

limb bud development and before the activa-

tion of SHH signaling in posterior restriction

of the basic helix-loop-helix transcription

factor dHAND. dHAND in turn prevents

Gli3 expression from spreading posteriorly

(Fig. 1A, panel 1) (7). In addition, GLI3

restricts the SHH-independent early expres-

sion of 5⬘HoxD genes and Gremlin to the

posterior mesenchyme (8). Subsequently,

dHAND functions in the activation of Shh

expression (9). Limb bud morphogenesis is

then controlled by reciprocal interactions of

two signaling centers (Fig. 1A, panel 2): the

polarizing region, an instructive organizer lo-

cated in the posterior limb bud mesenchyme,

and the apical ectodermal ridge (AER). SHH

signaling by the polarizing region in combi-

nation with bone morphogenetic proteins

Department of Developmental Biology, Faculty of

Biology, Utrecht University, Padualaan 8, NL-3584 CH

Utrecht, Netherlands.

Hubrecht Laboratorium, Upp-

salalaan 8, NL-3584 CT Utrecht, Netherlands.

*To whom correspondence should be addressed. E-

mail: R.Zeller@bio.uu.nl

R EPORTS

www.sciencemag.org SCIENCE VOL 298 25 OCTOBER 2002 827

on February 4, 2013www.sciencemag.orgDownloaded from